package 算法.链表;

import java.util.Stack;

public class TreeNode {
    Node root = null;
    Integer size;

    public Integer getSize() {
        return size;
    }

    public void setSize(Integer size) {
        this.size = size;
    }

    class Node {

        Node Lnode;
        Node Rnode;
        Integer value;

        public Node(Integer value) {
            this.value = value;
            this.Lnode = null;
            this.Rnode = null;
        }
    }

    public void PutV(int temp) {
        if (root == null) {
            root = new Node(temp);
            size = 1;
            return;
        }
        Node n = root;
        while (true) {
            if (Integer.compare(n.value, temp) > 0) {
                if (n.Lnode != null)
                    n = n.Lnode;
                else {
                    n.Lnode = new Node(temp);
                    break;
                }
            } else {
                if (n.Rnode != null)
                    n = n.Rnode;
                else {
                    n.Rnode = new Node(temp);
                    break;
                }
            }
        }
        size++;
    }

    public Integer[] PreOrder() {
        Integer[] list = new Integer[size];
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        int i = 0;
        while (!stack.empty()) {
            Node peek = stack.pop();
            if (peek.Rnode != null)
                stack.push(peek.Rnode);
            if (peek.Lnode != null) {
                stack.push(peek.Lnode);
            }
            list[i++] = peek.value;
        }
        return list;
    }

    public Integer[] MidOrder() {
        Integer[] list = new Integer[size];
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        Node node = root;
        int i = 0;
        while (node.Lnode != null) {  // 从根节点开始，将所有是左子树压入栈中（找到最左的叶子节点）
            stack.push(node.Lnode);
            node = node.Lnode;
        }
        // 从最左的叶子节点开始遍历
        while (!stack.empty()) {
            Node pop = stack.pop(); // 弹出当前栈顶结点
            if (pop.Rnode != null) { // 判断右子树是否为空
                stack.push(pop.Rnode);   //将右节点压入栈中
                if (pop.Rnode.Lnode != null) // 将右子树是的左子树依次加入栈中
                {
                    node = pop.Rnode;
                    while (node.Lnode != null) {  // 从此结点开始，将所有是左子树压入栈中
                        stack.push(node.Lnode);
                        node = node.Lnode;
                    }
                }
            }
            list[i++] = pop.value;
        }
        return list;
    }

    /**
     *  先求出 逆后序 （中 右 左），再逆序输出
     */
    public Integer[] PostOrder() {    // 左右中<-- 右左中<-->中左右
        Integer[] list = new Integer[size];
        Stack<Node> stack = new Stack<>();
        Stack<Integer> temp = new Stack<>();
        stack.push(root);
        int i = 0;
        while (!stack.empty()) {
            Node peek = stack.pop();
            if (peek.Lnode != null) {  // 后遍历左子树
                stack.push(peek.Lnode);
            }
            if (peek.Rnode != null) {
                stack.push(peek.Rnode);
            }
            temp.push(peek.value); // 将逆后序结果压入临时栈
        }
        while (!temp.empty())
            list[i++] = temp.pop();
        return list;
    }
}
